package leetcode.problems;

import org.junit.Test;

import java.util.Arrays;
import java.util.Stack;

/**
 * Created by gmwang on 2018/7/25
 * 转置矩阵
 */
public class _0803SortArrayByParityII {
    /**
     * Given an array A of non-negative integers, half of the integers in A are odd, and half of the integers are even.
       给定一个非负整数的数组A，A中的整数的一半是奇数，整数的一半是偶数。
       Sort the array so that whenever A[i] is odd, i is odd; and whenever A[i] is even, i is even.
      对数组进行排序，以便每当[i]是奇数时，i是奇数；每当i都是偶数时，i是偶数。
      You may return any answer array that satisfies this condition.
      您可以返回满足此条件的任何数组。
     Example 1:
     Input: [4,2,5,7]
     Output: [4,5,2,7]
     Explanation: [4,7,2,5], [2,5,4,7], [2,7,4,5] would also have been accepted.

     Note:
     2 <= A.length <= 20000
     A.length % 2 == 0
     0 <= A[i] <= 1000
     *
    /**
     *
     * @param A,B
     * @return
     */
    public int[] sortArrayByParityII(int[] A) {
        int odd = 0;
        int even = 0;
        Stack<Object> odds = new Stack<>();
        Stack<Object> evens = new Stack<>();
        int res [] = new int[A.length];
        for (int i = 0; i < A.length; i++) {
            //偶数
            if((A[i]&1) != 1){
                odd++;
                odds.add(A[i]);
            }else{
                even++;
                evens.add(A[i]);
            }
        }
        //如果超过2个
        if(odd > even + 1 || even > odd + 1){
            return res;
        }
        for (int i = 0; i < res.length; i++) {
            int pop= 0;
            //偶数
            if((i&1) != 1){
                pop = (int) odds.pop();
            }else{
                pop = (int) evens.pop();
            }
            res[i] = pop;
        }
        return res;
    }

//    public int[] sortArrayByParityII2(int[] A) {
//        int odd = 0;
//        int even = 0;
//        Stack<Object> odds = new Stack<>();
//        Stack<Object> evens = new Stack<>();
//        int res [] = new int[A.length];
//        for (int i = 0; i < A.length; i++) {
//            int k = 200000;
//            if(odds.size() > evens.size() + 2 || evens.size() > odds.size() + 2){
//                return null;
//            }
//            //i 偶数 A[i]也是偶数
//            if((A[i]&1) != 1 && (i&1) != 1){
//                k = A[i];
//                // i 奇数 A[i] 偶数
//            }else if((A[i]&1) != 1 && (i&1) == 1){
//                evens.add(A[i]);
//                if(!odds.isEmpty())
//                k = (int)odds.pop();
//
//                // i 偶数 A[i] 奇数
//            }else if((A[i]&1) == 1 && (i&1) != 1){
//                odds.add(A[i]);
//                if(!evens.isEmpty())
//                k = (int)evens.pop();
//                // i 奇数 A[i] 偶数
//            }else{
//                k= A[i];
//            }
//            res[i] = k;
//            if(i > 0 && (i&1) != 1){
//                if(res[i - 1] == 200000 ){
//                    if(!odds.isEmpty()){
//                        res[i - 1] = (int)odds.pop();
//                    }else {
//                        if(odd != 0) System.out.println("已经odd");
//                        odd = i;
//                    }
//                }
//            }
//            if(i > 0 && (i&1) == 1){
//                if(res[i - 1] == 200000){
//                    if(!evens.isEmpty())
//                    res[i - 1] = (int)evens.pop();
//                }else {
////                    if(even != 0){
//                        if(!evens.isEmpty())
//                        res[even] = (int)evens.pop();
//                        System.out.println("已经 even");
//                        even = i;
////                    }
//                }
//            }
//        }
//        System.out.println("evens===>"+evens.size());
//        System.out.println("odds===>"+odds.size());
//        if(!evens.isEmpty())
//        res[odd] = (int)evens.pop();
//        if(!odds.isEmpty())
//        res[even] = (int)odds.pop();
//        return res;
//    }
    @Test
    public void test() {
//        int[] ints = {4,2,5,7};
//        int[] ints = {3,1,4,2};
        int[] ints = {3,0,4,0,2,1,3,1,3,4};
        int[] res = sortArrayByParityII(ints);
        System.out.println(Arrays.toString(res));
    }
}
